//https://leetcode.cn/problems/stone-game-vii/description/?envType=daily-question&envId=2024-02-03



class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<vector<int>> dp(n, vector<int>(n));
        vector<int> sum(n + 1);
        for(int i = 1; i <= n; i++)
            sum[i] = stones[i - 1] + sum[i - 1];
        for(int i = 1; i < n; i++)
            for(int j =0; j + i < n; j++)
                dp[j][j + i] = max(
    sum[j + i + 1] - sum[j + 1] - dp[j + 1][j + i], // 移除左端石头
    sum[j + i] - sum[j] - dp[j][j + i - 1]          // 移除右端石头
                );
        return dp[0][n - 1];
    }
};


